package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.ArrayList;
import java.util.List;


/**
 * 5-opt
 */
public class Ls5opt extends LocalSearch {


    public Ls5opt(Problem problem) {
        super(problem);
    }

    @Override
    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("local search 5opt init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("local search 5opt final", finalSolution);
        CheckUtils.check(finalSolution, distance);
    }


    @Override
    protected Solution improve(Solution solution) {
        int n = solution.length();
        Solution currentSolution = solution.copy();

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        for (int m = l + 1; m < n; m++) {
                            List<Integer> currPath = new ArrayList<>(currentSolution.getPermutation());
                            int currCost = currentSolution.getCost();
                            List<List<Integer>> newPermutations = makeMove(currentSolution.getPermutation(), i, j, k, l, m);
                            for (List<Integer> path : newPermutations) {
                                int cost = calculateFitness(path);
                                if (cost < currCost) {
                                    currPath = path;
                                    currCost = cost;
                                }
                            }
                            if (currCost < currentSolution.getCost()) {
                                currentSolution = new Solution(currPath, currCost);
                            }
                        }
                    }
                }
            }
        }

        return currentSolution;
    }


    private List<List<Integer>> makeMove(List<Integer> permutation, int i, int j, int k, int l, int m) {
        List<Integer> A = new ArrayList<>(permutation.subList(0, j + 1));
        List<Integer> B = new ArrayList<>(permutation.subList(j + 1, k + 1));
        List<Integer> C = new ArrayList<>(permutation.subList(k + 1, l + 1));
        List<Integer> D = new ArrayList<>(permutation.subList(l + 1, m + 1));
        List<Integer> E = new ArrayList<>(permutation.subList(m + 1, permutation.size()));
        List<Integer> a = new ArrayList<>(permutation.subList(0, i + 1));
        a.addAll(reverse(permutation.subList(i + 1, j + 1)));
        List<Integer> b = reverse(B);
        List<Integer> c = reverse(C);
        List<Integer> d = reverse(D);
        List<Integer> e = reverse(E);

        List<List<Integer>> res = new ArrayList<>();
        // permutation
        res.add(merge(A, B, C, E, D));
        res.add(merge(A, B, D, C, E));
        res.add(merge(A, B, D, E, C));
        res.add(merge(A, B, E, D, C));
        res.add(merge(A, B, E, C, D));
        res.add(merge(A, C, B, D, E));
        res.add(merge(A, C, B, E, D));
        res.add(merge(A, C, D, B, E));
        res.add(merge(A, C, E, B, D));
        res.add(merge(A, D, B, C, E));
        res.add(merge(A, D, C, B, E));

        // 1
        res.add(merge(a, B, C, D, E));
        res.add(merge(a, B, C, E, D));
        res.add(merge(a, B, D, C, E));
        res.add(merge(a, B, D, E, C));
        res.add(merge(a, B, E, C, D));
        res.add(merge(a, B, E, D, C));
        res.add(merge(a, C, B, D, E));
        res.add(merge(a, C, B, E, D));
        res.add(merge(a, C, D, B, E));
        res.add(merge(a, C, E, B, D));
        res.add(merge(a, D, B, C, E));
        res.add(merge(a, D, C, B, E));

        res.add(merge(A, b, C, D, E));
        res.add(merge(A, b, C, E, D));
        res.add(merge(A, b, D, C, E));
        res.add(merge(A, b, D, E, C));
        res.add(merge(A, b, E, C, D));
        res.add(merge(A, b, E, D, C));
        res.add(merge(A, C, b, D, E));
        res.add(merge(A, C, b, E, D));
        res.add(merge(A, C, D, b, E));
        res.add(merge(A, C, E, b, D));
        res.add(merge(A, D, b, C, E));
        res.add(merge(A, D, C, b, E));

        res.add(merge(A, B, c, D, E));
        res.add(merge(A, B, c, E, D));
        res.add(merge(A, B, D, c, E));
        res.add(merge(A, B, D, E, c));
        res.add(merge(A, B, E, c, D));
        res.add(merge(A, B, E, D, c));
        res.add(merge(A, c, B, D, E));
        res.add(merge(A, c, B, E, D));
        res.add(merge(A, c, D, B, E));
        res.add(merge(A, c, E, B, D));
        res.add(merge(A, D, B, c, E));
        res.add(merge(A, D, c, B, E));

        res.add(merge(A, B, C, d, E));
        res.add(merge(A, B, C, E, d));
        res.add(merge(A, B, d, C, E));
        res.add(merge(A, B, d, E, C));
        res.add(merge(A, B, E, C, d));
        res.add(merge(A, B, E, d, C));
        res.add(merge(A, C, B, d, E));
        res.add(merge(A, C, B, E, d));
        res.add(merge(A, C, d, B, E));
        res.add(merge(A, C, E, B, d));
        res.add(merge(A, d, B, C, E));
        res.add(merge(A, d, C, B, E));

        res.add(merge(A, B, C, D, e));
        res.add(merge(A, B, C, e, D));
        res.add(merge(A, B, D, C, e));
        res.add(merge(A, B, D, e, C));
        res.add(merge(A, B, e, C, D));
        res.add(merge(A, B, e, D, C));
        res.add(merge(A, C, B, D, e));
        res.add(merge(A, C, B, e, D));
        res.add(merge(A, C, D, B, e));
        res.add(merge(A, C, e, B, D));
        res.add(merge(A, D, B, C, e));
        res.add(merge(A, D, C, B, e));

        // 2
        res.add(merge(a, b, C, E, D));
        res.add(merge(a, b, D, C, E));
        res.add(merge(a, b, D, E, C));
        res.add(merge(a, b, E, C, D));
        res.add(merge(a, b, E, D, C));
        res.add(merge(a, C, b, D, E));
        res.add(merge(a, C, b, E, D));
        res.add(merge(a, C, D, b, E));
        res.add(merge(a, C, E, b, D));
        res.add(merge(a, D, b, C, E));
        res.add(merge(a, D, C, b, E));

        res.add(merge(a, B, c, E, D));
        res.add(merge(a, B, D, c, E));
        res.add(merge(a, B, D, E, c));
        res.add(merge(a, B, E, c, D));
        res.add(merge(a, B, E, D, c));
        res.add(merge(a, c, B, D, E));
        res.add(merge(a, c, B, E, D));
        res.add(merge(a, c, D, B, E));
        res.add(merge(a, c, E, B, D));
        res.add(merge(a, D, B, c, E));
        res.add(merge(a, D, c, B, E));

        res.add(merge(a, B, C, E, d));
        res.add(merge(a, B, d, C, E));
        res.add(merge(a, B, d, E, C));
        res.add(merge(a, B, E, C, d));
        res.add(merge(a, B, E, d, C));
        res.add(merge(a, C, B, d, E));
        res.add(merge(a, C, B, E, d));
        res.add(merge(a, C, d, B, E));
        res.add(merge(a, C, E, B, d));
        res.add(merge(a, d, B, C, E));
        res.add(merge(a, d, C, B, E));

        res.add(merge(a, B, C, e, D));
        res.add(merge(a, B, D, C, e));
        res.add(merge(a, B, D, e, C));
        res.add(merge(a, B, e, C, D));
        res.add(merge(a, B, e, D, C));
        res.add(merge(a, C, B, D, e));
        res.add(merge(a, C, B, e, D));
        res.add(merge(a, C, D, B, e));
        res.add(merge(a, C, e, B, D));
        res.add(merge(a, D, B, C, e));
        res.add(merge(a, D, C, B, e));

        res.add(merge(A, b, c, D, E));
        res.add(merge(A, b, c, E, D));
        res.add(merge(A, b, D, c, E));
        res.add(merge(A, b, D, E, c));
        res.add(merge(A, b, E, c, D));
        res.add(merge(A, b, E, D, c));
        res.add(merge(A, c, b, D, E));
        res.add(merge(A, c, b, E, D));
        res.add(merge(A, c, D, b, E));
        res.add(merge(A, c, E, b, D));
        res.add(merge(A, D, b, c, E));
        res.add(merge(A, D, c, b, E));

        res.add(merge(A, b, C, d, E));
        res.add(merge(A, b, C, E, d));
        res.add(merge(A, b, d, C, E));
        res.add(merge(A, b, d, E, C));
        res.add(merge(A, b, E, C, d));
        res.add(merge(A, b, E, d, C));
        res.add(merge(A, C, b, d, E));
        res.add(merge(A, C, b, E, d));
        res.add(merge(A, d, b, C, E));
        res.add(merge(A, d, C, b, E));

        res.add(merge(A, b, C, D, e));
        res.add(merge(A, b, C, e, D));
        res.add(merge(A, b, D, C, e));
        res.add(merge(A, b, D, e, C));
        res.add(merge(A, b, e, C, D));
        res.add(merge(A, b, e, D, C));
        res.add(merge(A, C, b, D, e));
        res.add(merge(A, C, b, e, D));
        res.add(merge(A, C, D, b, e));
        res.add(merge(A, C, e, b, D));
        res.add(merge(A, D, b, C, e));
        res.add(merge(A, D, C, b, e));

        res.add(merge(A, B, c, d, E));
        res.add(merge(A, B, c, E, d));
        res.add(merge(A, B, d, c, E));
        res.add(merge(A, B, d, E, c));
        res.add(merge(A, B, E, d, c));
        res.add(merge(A, c, B, d, E));
        res.add(merge(A, c, B, E, d));
        res.add(merge(A, c, d, B, E));
        res.add(merge(A, c, E, B, d));
        res.add(merge(A, d, B, c, E));
        res.add(merge(A, d, c, B, E));

        res.add(merge(A, B, c, D, e));
        res.add(merge(A, B, c, e, D));
        res.add(merge(A, B, D, c, e));
        res.add(merge(A, B, D, e, c));
        res.add(merge(A, B, e, c, D));
        res.add(merge(A, B, e, D, c));
        res.add(merge(A, c, B, D, e));
        res.add(merge(A, c, B, e, D));
        res.add(merge(A, c, D, B, e));
        res.add(merge(A, c, e, B, D));
        res.add(merge(A, D, B, c, e));
        res.add(merge(A, D, c, B, e));

        res.add(merge(A, B, C, d, e));
        res.add(merge(A, B, C, e, d));
        res.add(merge(A, B, d, C, e));
        res.add(merge(A, B, d, e, C));
        res.add(merge(A, B, e, C, d));
        res.add(merge(A, B, e, d, C));
        res.add(merge(A, C, B, d, e));
        res.add(merge(A, C, B, e, d));
        res.add(merge(A, C, d, B, e));
        res.add(merge(A, C, e, B, d));
        res.add(merge(A, d, B, C, e));
        res.add(merge(A, d, C, B, e));

        // 3
        res.add(merge(a, b, c, E, D));
        res.add(merge(a, b, D, c, E));
        res.add(merge(a, b, D, E, c));
        res.add(merge(a, b, E, c, D));
        res.add(merge(a, b, E, D, c));
        res.add(merge(a, c, b, D, E));
        res.add(merge(a, c, b, E, D));
        res.add(merge(a, c, D, b, E));
        res.add(merge(a, c, E, b, D));
        res.add(merge(a, D, b, c, E));
        res.add(merge(a, D, c, b, E));

        res.add(merge(a, b, C, E, d));
        res.add(merge(a, b, d, C, E));
        res.add(merge(a, b, d, E, C));
        res.add(merge(a, b, E, C, d));
        res.add(merge(a, b, E, d, C));
        res.add(merge(a, C, b, d, E));
        res.add(merge(a, C, b, E, d));
        res.add(merge(a, C, d, b, E));
        res.add(merge(a, C, E, b, d));
        res.add(merge(a, d, b, C, E));
        res.add(merge(a, d, C, b, E));

        res.add(merge(a, b, C, e, D));
        res.add(merge(a, b, D, C, e));
        res.add(merge(a, b, D, e, C));
        res.add(merge(a, b, e, C, D));
        res.add(merge(a, b, e, D, C));
        res.add(merge(a, C, b, D, e));
        res.add(merge(a, C, b, e, D));
        res.add(merge(a, C, D, b, e));
        res.add(merge(a, C, e, b, D));
        res.add(merge(a, D, b, C, e));
        res.add(merge(a, D, C, b, e));

        res.add(merge(a, B, c, E, d));
        res.add(merge(a, B, d, c, E));
        res.add(merge(a, B, d, E, c));
        res.add(merge(a, B, E, c, d));
        res.add(merge(a, B, E, d, c));
        res.add(merge(a, c, B, d, E));
        res.add(merge(a, c, B, E, d));
        res.add(merge(a, c, d, B, E));
        res.add(merge(a, c, E, B, d));
        res.add(merge(a, d, B, c, E));
        res.add(merge(a, d, c, B, E));

        res.add(merge(a, B, c, e, D));
        res.add(merge(a, B, D, c, e));
        res.add(merge(a, B, D, e, c));
        res.add(merge(a, B, e, c, D));
        res.add(merge(a, B, e, D, c));
        res.add(merge(a, c, B, D, e));
        res.add(merge(a, c, B, e, D));
        res.add(merge(a, c, D, B, e));
        res.add(merge(a, c, e, B, D));
        res.add(merge(a, D, B, c, e));
        res.add(merge(a, D, c, B, e));

        res.add(merge(a, B, C, e, d));
        res.add(merge(a, B, d, C, e));
        res.add(merge(a, B, d, e, C));
        res.add(merge(a, B, e, C, d));
        res.add(merge(a, B, e, d, C));
        res.add(merge(a, C, B, d, e));
        res.add(merge(a, C, B, e, d));
        res.add(merge(a, C, d, B, e));
        res.add(merge(a, C, e, B, d));
        res.add(merge(a, d, B, C, e));
        res.add(merge(a, d, C, B, e));

        res.add(merge(A, b, c, d, E));
        res.add(merge(A, b, c, E, d));
        res.add(merge(A, b, d, c, E));
        res.add(merge(A, b, d, E, c));
        res.add(merge(A, b, E, c, d));
        res.add(merge(A, b, E, d, c));
        res.add(merge(A, c, b, d, E));
        res.add(merge(A, c, b, E, d));
        res.add(merge(A, c, d, b, E));
        res.add(merge(A, c, E, b, d));
        res.add(merge(A, d, b, c, E));
        res.add(merge(A, d, c, b, E));

        res.add(merge(A, b, c, D, e));
        res.add(merge(A, b, c, e, D));
        res.add(merge(A, b, D, c, e));
        res.add(merge(A, b, D, e, c));
        res.add(merge(A, b, e, c, D));
        res.add(merge(A, b, e, D, c));
        res.add(merge(A, c, b, D, e));
        res.add(merge(A, c, b, e, D));
        res.add(merge(A, c, D, b, e));
        res.add(merge(A, c, e, b, D));
        res.add(merge(A, D, b, c, e));
        res.add(merge(A, D, c, b, e));

        res.add(merge(A, b, C, d, e));
        res.add(merge(A, b, C, e, d));
        res.add(merge(A, b, d, C, e));
        res.add(merge(A, b, d, e, C));
        res.add(merge(A, b, e, C, d));
        res.add(merge(A, b, e, d, C));
        res.add(merge(A, C, b, d, e));
        res.add(merge(A, C, b, e, d));
        res.add(merge(A, C, d, b, e));
        res.add(merge(A, C, e, b, d));
        res.add(merge(A, d, b, C, e));
        res.add(merge(A, d, C, b, e));

        res.add(merge(A, B, c, d, e));
        res.add(merge(A, B, c, e, d));
        res.add(merge(A, B, d, c, e));
        res.add(merge(A, B, d, e, c));
        res.add(merge(A, B, e, c, d));
        res.add(merge(A, B, e, d, c));
        res.add(merge(A, c, B, d, e));
        res.add(merge(A, c, B, e, d));
        res.add(merge(A, c, d, B, e));
        res.add(merge(A, c, e, B, d));
        res.add(merge(A, d, B, c, e));
        res.add(merge(A, d, c, B, e));

        // 4
        res.add(merge(A, b, c, d, e));
        res.add(merge(A, b, c, e, d));
        res.add(merge(A, b, d, c, e));
        res.add(merge(A, b, d, e, c));
        res.add(merge(A, b, e, c, d));
        res.add(merge(A, b, e, d, c));
        res.add(merge(A, c, b, d, e));
        res.add(merge(A, c, b, e, d));
        res.add(merge(A, c, d, b, e));
        res.add(merge(A, c, e, b, d));
        res.add(merge(A, d, b, c, e));
        res.add(merge(A, d, c, b, e));

        res.add(merge(a, B, c, d, e));
        res.add(merge(a, B, c, e, d));
        res.add(merge(a, B, d, e, c));
        res.add(merge(a, B, d, c, e));
        res.add(merge(a, B, e, c, d));
        res.add(merge(a, B, e, d, c));
        res.add(merge(a, c, B, d, e));
        res.add(merge(a, c, B, e, d));
        res.add(merge(a, c, d, B, e));
        res.add(merge(a, c, e, B, d));
        res.add(merge(a, d, B, c, e));
        res.add(merge(a, d, c, B, e));

        res.add(merge(a, b, C, d, e));
        res.add(merge(a, b, C, e, d));
        res.add(merge(a, b, d, C, e));
        res.add(merge(a, b, d, e, C));
        res.add(merge(a, b, e, C, d));
        res.add(merge(a, b, e, d, C));
        res.add(merge(a, C, b, d, e));
        res.add(merge(a, C, b, e, d));
        res.add(merge(a, C, d, b, e));
        res.add(merge(a, C, e, b, d));
        res.add(merge(a, d, b, C, e));
        res.add(merge(a, d, C, b, e));

        res.add(merge(a, b, c, D, e));
        res.add(merge(a, b, c, e, D));
        res.add(merge(a, b, D, c, e));
        res.add(merge(a, b, D, e, c));
        res.add(merge(a, b, e, c, D));
        res.add(merge(a, b, e, D, c));
        res.add(merge(a, c, b, D, e));
        res.add(merge(a, c, b, e, D));
        res.add(merge(a, c, D, b, e));
        res.add(merge(a, c, e, b, D));
        res.add(merge(a, D, b, c, e));
        res.add(merge(a, D, c, b, e));

        res.add(merge(a, b, c, d, E));
        res.add(merge(a, b, c, E, d));
        res.add(merge(a, b, d, c, E));
        res.add(merge(a, b, d, E, c));
        res.add(merge(a, b, E, c, d));
        res.add(merge(a, b, E, d, c));
        res.add(merge(a, c, b, d, E));
        res.add(merge(a, c, b, E, d));
        res.add(merge(a, c, d, b, E));
        res.add(merge(a, c, E, b, d));
        res.add(merge(a, d, b, c, E));
        res.add(merge(a, d, c, b, E));

        // 5
        res.add(merge(a, b, c, d, e));
        res.add(merge(a, b, c, e, d));
        res.add(merge(a, b, d, c, e));
        res.add(merge(a, b, d, e, c));
        res.add(merge(a, b, e, c, d));
        res.add(merge(a, b, e, d, c));
        res.add(merge(a, c, b, d, e));
        res.add(merge(a, c, b, e, d));
        res.add(merge(a, c, d, b, e));
        res.add(merge(a, c, e, b, d));
        res.add(merge(a, d, b, c, e));
        res.add(merge(a, d, c, b, e));

        return res;
    }

    private List<Integer> merge(List<Integer> a, List<Integer> b, List<Integer> c, List<Integer> d, List<Integer> e) {
        List<Integer> s = new ArrayList<>();
        s.addAll(a);
        s.addAll(b);
        s.addAll(c);
        s.addAll(d);
        s.addAll(e);
        return s;
    }

    private List<Integer> reverse(List<Integer> s) {
        List<Integer> r = new ArrayList<>();
        for (int i = 0; i < s.size(); i++) {
            r.add(s.get(s.size() - 1 - i));
        }
        return r;
    }

}
